#include <stdio.h>
#include <stdlib.h>
#define PrintNodeWithPreAddr(m, p) PrintNode((m), (p), ((m)[(p)].pre_addr))
#define PrintNodeWithNextAddr(m, p) PrintNode((m), (p), ((m)[(p)].next_addr))
typedef struct elem{
    long pre_addr;
    int data;
    long next_addr;
} ElemType;

void PrintNode(ElemType MEM[], long p, long next);
void GetJumpNodes(ElemType MEM[], long JumpNodes[], long Head, unsigned int N, unsigned int K);
void OutputList(ElemType MEM[], long Head, unsigned int N);
void FixPre(ElemType MEM[], long Head, unsigned int *N);
void OutputList_R(ElemType MEM[], long Head, unsigned int N, unsigned int K);
void GetJumpNodes(ElemType MEM[], long JumpNodes[], long Head, unsigned int N, unsigned int K);

int main(){
    long Head = 0;
    unsigned int N = 0, K = 0;
    ElemType MEM[100000] = {{0, 0, 0}};
    //input head
    scanf("%ld %d %d", &Head, &N, &K);
    do{
        //input nodes
        ElemType t = {0, 0, 0};
        long addr = -1, p = -1;
        for (unsigned i = 0; i < N; i++){
            scanf("%ld %d %ld", &addr, &t.data, &t.next_addr);
            t.pre_addr = -1;
            MEM[addr] = t;
            p = addr;
        }
    } while (0);
    FixPre(MEM, Head, &N);
#ifdef DEBUG
    printf("Number of nodes %d\n", N);
    printf("Sorted List:\n");
    OutputList(MEM, Head, N);
    putchar('\n');
#endif
    OutputList_R(MEM, Head, N, K);
    return 0;
}

void PrintNode(ElemType MEM[], long p, long next){
    if (next != -1)
        printf("%05d %d %05d\n", p, MEM[p].data, next);
    else
        printf("%05d %d %d\n", p, MEM[p].data, next);
}

void OutputList(ElemType MEM[], long Head, unsigned int N){
    long p = Head;
    for (unsigned int i = 0; i < N; i++){
        PrintNodeWithNextAddr(MEM, p);
        p = MEM[p].next_addr;
    }
}
void FixPre(ElemType MEM[], long Head, unsigned int *N){
    long p = Head;

    long len = 1;
    if (p == -1)
        len = 0;
    else
        while (MEM[p].next_addr != -1){
            MEM[MEM[p].next_addr].pre_addr = p;
            p = MEM[p].next_addr;
            len++;
        }
    *N = len;
}
void OutputList_R(ElemType MEM[], long Head, unsigned int N, unsigned int K){
    long p = Head;
    long q = -1;
    long *JumpNodes = NULL;
    JumpNodes = malloc(sizeof(long) * (N / K));

    GetJumpNodes(MEM, JumpNodes, Head, N, K);

    for (int j = 0; j < N / K; j++){
        p = JumpNodes[j];
        //for each node in JumpNodes
        for (int i = 0; i < K - 1; i++){
            PrintNodeWithPreAddr(MEM, p);
            p = MEM[p].pre_addr;
        }
        if ((j + 1) < (N / K))
            PrintNode(MEM, p, JumpNodes[j + 1]);
        else{
            PrintNode(MEM, p, MEM[JumpNodes[j]].next_addr);
            p = MEM[JumpNodes[j]].next_addr;
            break;
        }
    }
    for (unsigned int i = 0; i < (N % K); i++){
        //剩下的元素
        PrintNodeWithNextAddr(MEM, p);
        p = MEM[p].next_addr;
    }
}
void GetJumpNodes(ElemType MEM[], long JumpNodes[], long Head, unsigned int N, unsigned int K){
    long p = Head;
    long q = -1;
    long JumpNodes_index = 0;
    for (unsigned int NK = 0; NK < N / K; NK++){
        //K整数倍的元素

        for (unsigned int i = 0; i < K - 1; i++)
            p = MEM[p].next_addr;
        JumpNodes[NK] = p;
        p = MEM[p].next_addr;
    }
#ifdef DEBUG
    printf("jump nodes:");
    for (unsigned int NK = 0; NK < N / K; NK++)
        printf("(%d) ", JumpNodes[NK]);
    putchar('\n');
#endif
}
